package main.Q701_800;

import java.util.*;

public class Q701_710 {
    public static void main(String[] args) {
        System.out.println("Question701：二叉搜索树中的插入操作");
        System.out.println("Question702：");
        System.out.println("Question703：数据流中的第 K 大元素");
        System.out.println("Question704：二分查找");
        System.out.println("Question705：");
        System.out.println("Question706：设计哈希映射");
        System.out.println("Question707：设计链表");
        System.out.println("Question708：");
        System.out.println("Question709：转成小写字母");
        System.out.println("Question710：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question701{
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode last=root,curNode=new TreeNode(val);
        if (last==null) return curNode;
        while (true){
            if (last.val<val&&last.right!=null) last=last.right;//滑动
            else if (last.val<val&&last.right==null) {//插入
                last.right=curNode;
                break;
            }else if (last.val>val&&last.left!=null) last=last.left;//滑动
            else if (last.val>val&&last.left==null) {//插入
                last.left=curNode;
                break;
            }
        }
        return root;
    }
}

class Question703{
    PriorityQueue<Integer> queue;
    int k;
    public Question703(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;
        for(int num : nums){
            queue.add(num);
        }
        while(queue.size() > k){
            queue.poll();
        }
    }

    public int add(int val) {
        queue.add(val);
        if(queue.size() > k){
            queue.poll();
        }
        return queue.peek();
    }
}

class Question704{
    public int search(int[] nums, int target) {
        int result=-1,left=0,right= nums.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target) {
                result=mid;
                break;
            } else if (nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return result;
    }
}

class Question706{
    Set<Integer> keySet;
    List<int[]> valueList;
    public Question706() {
        keySet=new HashSet<>();
        valueList=new ArrayList<>();
    }

    public void put(int key, int value) {
        int[] curKV=null;
        if (keySet.contains(key)){//keySet中存在key
            for (int[] KV:valueList)
                if (KV[0]==key){
                    curKV=KV;
                    break;
                }
            curKV[1]=value;
        }else {
            keySet.add(key);
            curKV=new int[]{key,value};
            valueList.add(curKV);
        }
    }

    public int get(int key) {
        int value=-1;
        if (keySet.contains(key)){
            for (int[] KV:valueList)
                if (KV[0]==key){
                    value=KV[1];
                    break;
                }
        }
        return value;
    }

    public void remove(int key) {
        Integer obj=key;
        if (keySet.contains(key)){
            keySet.remove(obj);
            int[] KVObj=null;
            for (int[] KV:valueList)
                if (KV[0]==key){
                    KVObj=KV;
                    break;
                }
            valueList.remove(KVObj);
        }
    }
}

class Question707{
    List<Integer> list;
    int size;
    public Question707() {
        list=new ArrayList<>();
        size=0;
    }

    public int get(int index) {
        if (index>=0&&index<size) return list.get(index);
        else return -1;
    }

    public void addAtHead(int val) {
        list.add(0,val);
        size++;
    }

    public void addAtTail(int val) {
        list.add(val);
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (size==index) addAtTail(val);
        else if (index<0) addAtHead(val);
        else if (0<=index&&index<size) {
            list.add(index,val);
            size++;
        }

    }

    public void deleteAtIndex(int index) {
        if (index>=0&&index<size) {
            list.remove(index);
            size--;
        }
    }
}

class Question709{
    public String toLowerCase(String s) {
        return s.toLowerCase();
    }
}